package 数据结构.LinkList.diamond;
/*问题：LeetCode141 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。

        如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 、
        为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
         1 -> 2 -> 3 -> 4 -> 5，pos = 2，表示链表的尾部节点 5 将连接到链表的第 2 个节点（即节点 3）。
        因此，链表将变成
         1 -> 2 -> 3 -> 4 -> 5 -> 3，形成一个环。
        注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

        如果链表中存在环 ，则返回 true 。 否则，返回 false 。
        输入：head = [3,2,0,-4], pos = 1
        输出：true
        */



//没有环：1.链表头节点为 null。
//       2.链表只有一个节点且其 next 为 null。
//       3.链表中节点的 next 指针最终指向 null。
 //todo   即：链表的尽头为null
//有环：其实就是：1.链表只有一个节点，且其 next 指针指向自己。
/*                   ListNode head = new ListNode(1);
                        head.next = head;*/
//              2.链表中某个节点的 next 指针指向前面某个节点（包括自己），形成环。
//例如：1 -> 2 -> 3 -> 4 -> 2，其中节点 4 的 next 指针指向节点 2，形成环。


//注意：在这道题的背后，其实有着pos和链表的设置，只是没体现而已，
// 后台会根据pos和链表如 1--2--3--4
// 然后去生成有/没环的链表： 1--2--3--4 --1 环
//                       1--2--3--4 没环
//然后再调用judge方法 传如此时的head 去判断
//然后再去判断这个1--2--3--4--1是不是环，而不是判断pos前的链表1--2--3--4 了



public class ifRing {
    public static class ListNode{
        int val;
     ListNode next;
    ListNode(int x) {
       val = x;
       next = null;
    }
    }

    public static void main(String[] args) {
/*        ListNode head=new ListNode(1);
        ListNode two=new ListNode(2);
        ListNode three=new ListNode(3);
        ListNode four=new ListNode(4);
        head.next=two;
        two.next=three;
        three.next=four;
        Boolean result=judge(head,2);*/

        // 创建带环链表
        int[] values = {1, 2, 3, 4, 5};
        int pos = 2; // 环的位置，尾节点连接到第 3 个节点（索引从 0 开始）
        ListNode head = createCycleList(values, pos);
        System.out.println(hasCycle(head));  // 输出 true

        // 创建不带环链表
        pos = -1; // 没有环
        head = createCycleList(values, pos);

        //上面是后台的 根据pos和链表创建的新链表

        //然后调用下面的方法去判断该链表是不是环
        System.out.println(hasCycle(head));  // 输出 false
    }
    //利用pos和链表创建一个可能是环的链表
    public static ListNode createCycleList(int[] values, int pos) {
        if (values == null || values.length == 0) return null;

        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        ListNode cycleEntry = null;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
            if (i == pos) {
                cycleEntry = current;  // 记录环的入口点
            }
        }

        if (pos >= 0) {
            current.next = cycleEntry;  // 创建环
        }

        return head;
    }
  /*  private static Boolean judge(ListNode head) {
        Long len=1l;
        ListNode tem=head;
        while (tem.next!=null){
            tem=tem.next;
            len++;
        }
        if(len>pos &&len>1){
            return true;
        }
        return false;
    }*/
    //判断链表是不是环
    public static boolean hasCycle(ListNode head) {
        //利用快慢指针思想：如果相遇则有环 不相遇则无环，
        // 无环的话：每个节点最多被访问两次 且会遇到链表的尽头为null的情况
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            //走两步
            fast=fast.next.next;
            //走一步
            slow=slow.next;
            if(fast==slow){
                return true;
            }

        }
        return false;
    }

    }
